package 动态规划;

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.IntStream;

public class No300最长递增子序列 {

    /**
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     *
     * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
     * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     *  
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * 示例 2：
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * 示例 3：
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     */

    //终极good法,二分法查找O(NlogN)
    public int lengthOfLISGood(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return len;
        }

        // tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        // 遍历第 1 个数，直接放在有序数组 tail 的开头
        tail[0] = nums[0];
        // end 表示有序数组 tail 的最后一个已经赋值元素的索引(即最长排序序列len)
        int end = 0;

        for (int i = 1; i < len; i++) {
            // 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大
            if (nums[i] > tail[end]) {
                // 直接添加在那个元素的后面，所以 end 先加 1
                end++;
                tail[end] = nums[i];
            } else {
                // 使用二分查找法，在有序数组 tail 中
                /**
                 * tail存的是len长度的最长子序列它的最小末尾数值
                 * 可能会替换到最后一个,所以必须进行二分替换
                 */
                int left = 0;
                int right = end;
                //在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
                while (left < right) {
                    // 选左中位数不是偶然，而是有原因的，原因请见 LeetCode 第 35 题题解
                    // int mid = left + (right - left) / 2;
                    int mid = (left+right)/2;
                    //tail数组里面是有序数组
                    if (tail[mid] < nums[i]) {
                        // 中位数肯定不是要找的数，把它写在分支的前面
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 走到这里是因为 第一个if 的反面，因此一定能找到第 1 个大于等于 nums[i] 的元素
                // 因此，无需再单独判断,为什么就直接替换了呢? 有序数组一定有一个
                tail[left] = nums[i];
            }
            // 调试方法
             printArray(nums[i], tail);
        }
        // 此时 end 是有序数组 tail 最后一个元素的索引
        // 题目要求返回的是长度，因此 +1 后返回
        end++;
        return end;
    }

    // 调试方法，以观察是否运行正确
    private void printArray(int num, int[] tail) {
        System.out.print("当前数字：" + num);
        System.out.print("\t当前 tail 数组：");
        int len = tail.length;
        for (int i = 0; i < len; i++) {
            if (tail[i] == 0) {
                break;
            }
            System.out.print(tail[i] + ", ");
        }
        System.out.println();
    }

    public int lengthOfLIS(int[] nums) {
        /**
         * 使用db存储当前最长的子序列
         */
        int[] db=new int[nums.length];
        int resultMax=1;
        db[0]=1;
        for (int i = 1; i < nums.length; i++) {
            int max=0;
            for (int j = i-1; j >= max; j--) {
                if(nums[i]>nums[j]){
                    //当前元素大于已经扫描过的元素
                    max=Math.max(db[j],max);
                }
            }
            db[i]=max+1;//为什么一定+1呢?因为for里面的if条件是大于已经扫描过的元素
            resultMax=Math.max(db[i],resultMax);
        }

        return resultMax;
    }

    //低级版的,非优化for(比较容易想)
    public int lengthOfLISLower(int[] nums) {
        /**
         * 使用db存储当前最长的子序列
         */
        int[] db=new int[nums.length];
        int resultMax=1;
        db[0]=1;
        for (int i = 1; i < nums.length; i++) {
            //这里需要为0
            int max=0;
            //此处for的条件可以优化
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]) {
                    //比别人大才能吃掉别人
                    max = Math.max(max, db[j]);
                }
            }
            db[i]=max+1;//为什么一定+1呢?因为for里面的if条件是大于已经扫描过的元素
            resultMax=Math.max(db[i],resultMax);
        }

        return resultMax;
    }

    public static void main(String[] args) {
        No300最长递增子序列 n=new No300最长递增子序列();
        int[] arr={3, 5, 6, 2, 5, 4};
//        int[] arr={3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12};
        int result = n.lengthOfLISGood(arr);
        System.out.println(result);
    }

}
